package bm34;

import javax.swing.tree.TreeNode;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/8/11 2:33
 * BM34. 判断是否为二叉搜索树
 * https://www.nowcoder.com/practice/a69242b39baf45dea217815c7dedb52b?tpId=295&tqId=2288088&ru=%2Fpractice%2F8a2b2bf6c19b4f23a9bdb9b233eefa73&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {

    private int preVal = Integer.MIN_VALUE; // 记录前驱值

    // 二叉搜索树的中序遍历思路
    public boolean isValidBST (TreeNode root) {
        if (root == null) {
            return true;
        }
        // 进入左子树
        if (!isValidBST(root.left)) {
            return false;
        }
        if (preVal > root.val) {
            return false;
        }
        // 更新前驱
        preVal = root.val;
        // 进入右子树
        return isValidBST(root.right);
    }

    private class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
}
